﻿using System;
using System.Collections.Generic;
using IListNode;

namespace _94_binary_tree_inorder_traversal
{
    class Program
    {
        static void Main (string[] args)
        {
            TreeNode root = new TreeNode (1);
            root.left = new TreeNode (2);
            root.right = new TreeNode (3);
            root.right.left = new TreeNode (4);
            root.right.right = new TreeNode (5);

            List<int> nums = new List<int> ();
            //nums = InorderTraversal (root);
            nums = InorderRZ (root);

            for (int i = 0;i < nums.Count;i++)
            {
                Console.Write ($"{nums[i]} ");
            }
        }

        private static List<int> num = new List<int> ();
        public static List<int> InorderTraversal (TreeNode root)
        {
            InOrder (root);
            return num;
        }

        public static void InOrder(TreeNode t)
        {
            if (t != null)
            {
                InorderTraversal (t.left);
                num.Add (t.val);
                InorderTraversal (t.right);
            }
        }


        public static List<int> InorderRZ (TreeNode root)
        {
            List<int> result = new List<int> ();
            Stack<TreeNode> stack = new Stack<TreeNode> ();
            TreeNode node = root;
            while(node != null || stack.Count > 0)
            {
                while(node != null)
                {
                    stack.Push (node);
                    node = node.left;
                }
                node = stack.Pop ();
                result.Add (node.val);
                node = node.right;
            }

            return result;
        }
    }
}
